package leetcode.code0525;

import leetcode.helper.MaxDebug;

public class Solution extends Solution525 {

	@Override
	public int findMaxLength(int[] nums) {
		int LEN = nums.length;
		int[] sum = new int[LEN + 1];// nums[0,i-1]上1的数量
		Integer[] hash = new Integer[(LEN << 1) + 1];
		hash[LEN] = 0;
		int max = 0;// 结果
		for (int i = 1; i <= LEN; i++) {
			int curSum = sum[i - 1] + nums[i - 1];
			sum[i] = curSum;
			int id = i - (curSum << 1) + LEN;
			if (hash[id] == null) {
				hash[id] = i;
			} else {
				max = Math.max(max, i - hash[id]);
			}
		}
		return max;//
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug6();
		so.debug5();
		MaxDebug.debug14(so);
//		int[] debug = new int[100];
//		for (int i = 0; i < 100; i++) {
//			debug[i] = (int) (Math.random() * 2);
//		}
//		H.printObject(debug);
//		System.out.println(so.findMaxLength(debug));
//		int[] input = H.str2array3(
//				"[0,1,0,1,1,1,0,0,1,1,0,1,1,1,1,1,1,0,1,1,0,1,1,0,0,0,1,0,1,0,0,1,0,1,1,1,1,1,1,0,0,0,0,1,0,0,0,1,1,1,0,1,0,0,1,1,1,1,1,0,0,1,1,1,1,0,0,1,0,1,1,0,0,0,0,0,0,1,0,1,0,1,1,0,0,1,1,0,1,1,1,1,0,1,1,0,0,0,1,1]");
//		so.f(input);
	}

	public void f(int[] input) {
		int len = input.length;
		int max = 0;
		int l = 0, r = 0;
		for (int i = 0; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				int cur = this.ff(input, i, j);
				if (cur > max) {
					max = cur;
					l = i;
					r = j;
				}
			}
		}
		System.out.println(max + " " + l + " " + r);
	}

	private int ff(int[] input, int i, int j) {
		int one = 0;
		for (int m = i; m <= j; i++) {
			if (input[m] == 1) {
				one++;
			} else {
				one--;
			}
		}
		return one == 0 ? j - i + 1 : 0;
	}

}
